import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created with Intellij IDEA.
 * Description;
 * User:墨琦
 * Data:2023-09-19
 * Time:14:49
 */
public class Text1 {
    //全为正数的情况
    public List<List<Integer>> fourSum2(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> list=new ArrayList<>();

        for(int s1=0;s1<nums.length-3;s1++)
        {
            if(target>0&&nums[s1]>target)
                break;
            if(s1>=1&&nums[s1]==nums[s1-1])
            {
                continue;
            }
            int aim=target-nums[s1];
            for(int s2=s1+1;s2<nums.length-2;s2++)
            {
                if(s2>s1+1&&nums[s2]==nums[s2-1])
                {
                    continue;
                }
                int sum=nums[s1]+nums[s2];
                if(target>0&&sum>target)
                {
                    break;
                }
                int left=s2+1,right=nums.length-1;
                int aim2=aim-nums[s2];
                while(left<right)
                {
                    int aim3=aim2-nums[left];
                    if(Arrays.binarySearch(nums,left,right,aim3)>-1)
                    {
                        int count=Arrays.binarySearch(nums,left,right,aim3);
                        list.add(new ArrayList<Integer>(Arrays.asList(nums[s1],nums[s2],nums[left],nums[count])));
                        left++;
                        while(left<right&&nums[left]==nums[left-1]) left++;
                    }
                    else left++;
                }

            }
        }

        return list;
    }
    //无论是什么数
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> list=new ArrayList<>();
        for(int s1=0;s1<nums.length-3;s1++)
        {
            if(target>0&&nums[s1]>target)
                break;
            if(s1>=1&&nums[s1]==nums[s1-1])
            {
                continue;
            }
            for(int s2=s1+1;s2<nums.length-2;s2++)
            {
                if(s2>s1+1&&nums[s2]==nums[s2-1])
                {
                    continue;
                }
                int sum=nums[s1]+nums[s2];
                if(target>0&&sum>target)
                {
                    break;
                }
                int left=s2+1,right=nums.length-1;
                while(left<right)
                {
                    if(nums[left]+nums[right]+sum>target)
                    {
                        right--;
                    }
                    else if(nums[left]+nums[right]+sum<target)
                    {
                        left++;
                    }
                    else if(nums[left]+nums[right]+sum==target)
                    {
                        list.add(new ArrayList<Integer>(Arrays.asList(nums[s1],nums[s2],nums[left],nums[right])));
                        left++;right--;
                        while(left<right&&nums[left]==nums[left-1]) left++;
                        while(left<right&& nums[right]==nums[right+1]) right--;
                    }

                }
            }
        }
        return list;
    }

    public static void main(String[] args) {
        Text1 kk=new Text1();
        kk.fourSum2(new int[]{1,2,3,4,5,6,7,8,9},10);

    }
}
